package day1_array.my_array;

import java.util.Arrays;

/**
 * 自己实现基于int的顺序表
 */
public class SeqList {
    private int size;
    private int[] elementData;
    private static final int DEFAULT_CAPACITY = 10;

    public SeqList() {
        this.elementData = new int[DEFAULT_CAPACITY];
    }

    public SeqList(int initCapacity) {
        this.elementData = new int[initCapacity];
    }

    public void addLast(int value) {
        addIndex(size,value);
    }

    public void addFirst(int value) {
        addIndex(0,value);
    }

    public void addIndex(int index,int value) {
        if (index < 0 || index > size) {
            System.out.println("插入索引非法，index >=0 且 <= size");
            return;
        }
        if (size == elementData.length) {
            grow(size);
        }
        // 将index之后的元素统一向后移动一个单位
        for (int i = size - 1; i >= index; i--) {
            elementData[i + 1] = elementData[i];
        }
        // 此时index位置已经空出来
        elementData[index] = value;
        size++;
    }

    /**
     * 删除顺序表中指定位置的元素
     * @param index
     * @return
     */
    public boolean removeIndex(int index) {
        if (!rangeCheck(index)) {
            System.out.println("刪除索引非法,index >=0 且 < size");
            return false;
        }
        // 需要将index+1之后的元素统一向前移动一个单位
        for (int i = index; i < size - 1; i++) {
            elementData[i] = elementData[i + 1];
        }
        size --;
        // 每次搬移数据后，最后一个元素仍然还在，需要重置为0
        elementData[size] = 0;
        return true;
    }

    /**
     * 删除顺序表中所有给定元素value
     * @param value
     * @return
     */
    public boolean removeValue(int value) {
        boolean isValueContains = false;
        for (int i = 0; i < size; i++) {
            // 若出现重复元素，需要删除多次,同时需要检验，
            // 若删除后有效元素已经小于当前索引i的情况
            while (i != size && elementData[i] == value) {
                isValueContains = true;
                // 删除i对应的索引下标
                removeIndex(i);
            }
        }
        return isValueContains;
    }

    public boolean removeFirst() {
        return removeIndex(0);
    }

    public boolean removeLast() {
        return removeIndex(size - 1);
    }

    /**
     * 将指定索引位置元素修改为新值
     * @param index
     * @param newValue
     * @return
     */
    public int set(int index,int newValue) {
        if (rangeCheck(index)) {
            int oldVal = elementData[index];
            elementData[index] = newValue;
            return oldVal;
        }
        return -1;
    }

    public int find(int value) {
        for (int i = 0; i < size; i++) {
            if (elementData[i] == value) {
                return i;
            }
        }
        return -1;
    }

    public boolean contains(int value) {
        int index = find(value);
        return index != -1;
    }

    public int get(int index) {
        if (rangeCheck(index)) {
            return elementData[index];
        }
        return -1;
    }

    private boolean rangeCheck(int index) {
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }


    private void grow(int oldCapacity) {
        int newCapacity = oldCapacity << 1;
        elementData = Arrays.copyOf(elementData,newCapacity);
    }


    /**
     * 将顺序表序列化为字符串
     * @return
     */
    public String toString() {
        String ret = "[";
        for (int i = 0; i < size; i++) {
            ret += elementData[i];
            if (i != size - 1) {
                ret += ", ";
            }
        }
        ret += "]";
        return ret;
    }

    public int getSize() {
        return size;
    }

    /**
     * 还原顺序表
     */
    public void clear() {
        Arrays.fill(elementData,0);
    }

    public static void main(String[] args) {
        SeqList seqList = new SeqList();
        seqList.addLast(2);
        seqList.addLast(2);
        seqList.addLast(2);
        seqList.addLast(1);
        seqList.removeValue(2);
        System.out.println(seqList);
    }

}
